# Линейный список

Линейный список представляет собой последовательность \\(n \geq 0\\) узлов \\(X\_{1}, X\_{2}, ... , X\_{n}\\), 
важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, 
как будто они находятся на одной линии. 
Иначе говоря, в такой структуре должно соблюдаться следующее условие: 
если \\(n > 0\\) и \\(X\_{1}\\) является первым узлом, а \\(X\_{n}\\) — последним, 
то k-й узел \\(X\_{k}\\) следует за \\(X\_{k − 1}\\) и предшествует узлу \\(X\_{k + 1}\\) для всех \\(1 < k < n\\).

С линейными списками могут выполняться следующие операции.

1. Получение доступа к k-му узлу списка для проверки и/или изменения содержимого его полей.
2. Вставка нового узла сразу после или до k-го узла.
3. Удаление k-го узла.
4. Объединение в одном списке двух (или более) линейных списков.
5. Разбиение линейного списка на два (или более) списка.
6. Создание копии линейного списка.
7. Определение количества узлов в списке.
8. Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
9. Поиск узла с заданным значением в некотором поле.

---

**Ссылки:**

- [Donald E. Knuth - The Art of Computer Programming, section 2.2.1](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
